/**
 * 【动态规划】最大子字符串
 * @param {String} stringA 
 * @param {String} stringB 
 * @returns {string} result
 */
export const longestSubString = (stringA, stringB) => {
    // 字符串B的每个字母组成二维数组的列
    const matrix = [new Array(stringB.length + 1).fill(0)]
    // 字符串A的每个字母组成二维数组的行
    for (let i = 1; i < stringA.length + 1; i++) {
        matrix[i] = [0]
        for (let j = 1; j < stringB.length + 1; j++) {
            if (stringA[i - 1] === stringB[j - 1]) {
                // 如果当前位置在两个字符串上的字母相同，则发现相同子串的项，当前最大子串长度 + 1
                // 当前最大子串长度的数值在当前位置的 *左上角* 上
                matrix[i][j] = matrix[i - 1][j - 1] + 1
            } else {
                // 如果当前位置在两个字符串上字母不相同，则没有发现相同子串的项
                // 当前情况下最大子串长度要么在当前位置的 *上方* 或者 *左方*
                matrix[i][j] = Math.max(matrix[i - 1][j], matrix[i][j - 1])
            }
        }
    }
    console.log(matrix)
    console.log(matrix[stringA.length][stringB.length])
    return getLongestSubString(matrix, stringA, stringB, stringA.length, stringB.length)
}

/**
 * 获取最大子字符串
 * @param {Array<Array<Number>>} matrix 
 * @param {string} stringA 
 * @param {string} stringB 
 * @returns {string} result
 */
const getLongestSubString = (matrix, stringA, stringB, i, j) => {
    if (i === 0 || j === 0) {
        return ''
    }
    // 如果发现当前矩阵位置在字符串中字符相同，则将该字符拼在结果结尾
    if (stringA[i - 1] === stringB[j - 1]) {
        return getLongestSubString(matrix, stringA, stringB, i - 1, j - 1) + stringA[i - 1]
    } else {
        // 如果当前位置在字符串中位置不同，去判断矩阵中记录的最大子串长度在哪边，那边长，最大子串的下一位就在哪里，往大的方向递归拼接，直至已经找到字符串的头了
        if (matrix[i][j - 1] > matrix[i - 1][j]) {
            return getLongestSubString(matrix, stringA, stringB, i, j - 1)
        } else {
            return getLongestSubString(matrix, stringA, stringB, i - 1, j)
        }
    }
}